package cn.zl.orchestra.common;


import java.util.*;
import java.util.stream.Collectors;

/**
 * 服务编排 dag
 * <p>
 * <p>
 * 1. 存储 各个节点的 id
 * 2. 遍历功能，可以将 dag 图转换成list形式输出
 *
 * @author zhong lin  2022/8/19
 */
public class OrchestraDag {

    /**
     * node linked
     */
    private final LinkedList<Long> nodeLinkedList;

    public OrchestraDag(List<EdgeMeta> edgeList) {
        nodeLinkedList = topologicalSortImpl(edgeList);
    }

    /**
     * 取出 dag 图中，第一个节点ID
     *
     * @return 节点ID
     */
    public Long popApiId() {
        return nodeLinkedList.pop();
    }

    public boolean haveNext() {
        return !nodeLinkedList.isEmpty();
    }

    private LinkedList<Long> topologicalSortImpl(List<EdgeMeta> edgeList) {
        //入度为0的结点队列
        Queue<Long> zeroIndegreeVertexQueue = new LinkedList<>();
        //保存结果
        LinkedList<Long> topoResultList = new LinkedList<>();
        //保存入度不为0的结点
        Map<Long, Integer> notZeroIndegreeVertexMap = new HashMap<>();

        Map<Long, EdgeMeta> dagMap = edgeList.stream().collect(Collectors.toMap(EdgeMeta::getCurrentId, e -> e));

        Map<Long, Integer> dagIndegreeMap = edgeList.stream().collect(Collectors.toMap(EdgeMeta::getCurrentId, e -> e.getParentIds().size()));


        //扫描所有的顶点,将入度为0的顶点入队列
        for (Long nodeId : dagIndegreeMap.keySet()) {
            int inDegree = getIndegree(nodeId, dagIndegreeMap);

            if (inDegree == 0) {
                zeroIndegreeVertexQueue.add(nodeId);
                topoResultList.add(nodeId);
            } else {
                notZeroIndegreeVertexMap.put(nodeId, inDegree);
            }
        }

        //采用topology算法, 删除入度为0的结点和它的关联边
        while (!zeroIndegreeVertexQueue.isEmpty()) {
            Long v = zeroIndegreeVertexQueue.poll();
            //得到相邻结点
            Set<Long> subsequentNodes = getSubsequentNodes(v, dagMap);

            for (Long subsequentVertex : subsequentNodes) {

                Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

                if (--degree == 0) {
                    topoResultList.add(subsequentVertex);
                    zeroIndegreeVertexQueue.add(subsequentVertex);
                    notZeroIndegreeVertexMap.remove(subsequentVertex);
                } else {
                    notZeroIndegreeVertexMap.put(subsequentVertex, degree);
                }

            }
        }

        //notZeroIndegreeVertexMap如果为空, 表示没有环
        return topoResultList;
    }

    private Set<Long> getSubsequentNodes(Long v, Map<Long, EdgeMeta> dagMap) {
        EdgeMeta edgeMeta = dagMap.get(v);

        return new HashSet<>(edgeMeta.getTargetIds());

    }

    private int getIndegree(Long nodeId, Map<Long, Integer> dagMap) {
        return dagMap.get(nodeId);
    }
}
